Từ năm 1863, ông được cử ra Bắc Kỳ đánh dẹp quân Lê Duy Phụng.

Năm Tự Đức thứ 25 (1870), quân Cờ Đen Lưu Vĩnh Phúc vẫn đánh phá cướp bóc các tỉnh Thái Nguyên, Lạng Sơn, Cao Bằng, Trong 3 năm trường chúng vẫn uy hiếp các tỉnh này và quan quân liên tục thất bại.

Sau khi quan Tổng đốc Phạm Chi Hương bại trận và bị bắt, triều đình đã phái Võ Trọng Bình ra làm Tổng đốc Hà Ninh kiêm Khâm sai Quân thứ đại thần Tuyên-Thái-Lạng. Quan Khâm sai hội với quan Đề đốc Quảng Tây để cùng đánh quân Ngô Côn vì họ cứ quấy phá cả hai bên biên thùy. Vào giữa năm 1869, Ngô Côn đem quân đánh Bắc Ninh, quan Tiểu phủ Ông Ích Khiêm đánh thắng một trận lớn, phá tan quân giặc và Ngô Côn bị bắn chết.

Ngô Côn chết rồi thì đồng đảng chia làm 3 phe tiếp tục cướp phá các tỉnh mạn ngược ở miền Bắc: phe Cờ Đen của Lưu Vĩnh Phúc, phe Cờ Vàng của tướng Hoàng Sùng Anh, phe Cờ Trắng của Bàn Văn Nhị và Lương Văn Lợi.

Quan Trung quân Đoàn Thọ được gửi từ Kinh ra làm Tổng thống quân vụ Bắc Kỳ. Ông liền kéo quân lên Lạng Sơn. Bọn giặc Khách là Tô Tứ thình lình nổi lên nửa đêm vào chiếm thành giết chết Đoàn Thọ. Võ Trọng Bình may mắn chạy thoát được. Triều đình Huế lại sai Hoàng Kế Viêm ra làm Thống đốc quân vụ Lạng-Bình-Ninh-Thái cùng với Tán tương Tôn Thất Thuyết tìm cách dẹp giặc cho yên. Tiếp theo vua lại sai ông Lê Tuấn là Thượng thơ Hình bộ ra làm Khâm sai thị sự để giúp Hoàng Kế Viêm. Rồi Hoàng Kế Viêm giữ mạn Sơn Tây, Lê Tuấn trấn đóng ở Hải Dương. Tuy vậy tình hình vẫn lằng nhằng không giải quyết thanh thỏa được.

Vua Tự Đức quá lo lắng, lại phải vời Nguyễn Tri Phương cho làm chức Tam tuyên quân thứ Khâm mạng Đại thần, được phép tùy nghi lo việc đánh dẹp cho yên. Vua ban cho ông kỳ bài, ấn kiếm, cờ mao tiết, nhung y, v.v. Đến miền Bắc, ông và Hoàng Kế Viêm chủ trương chia để trị, thu phục quân Cờ Đen vì lực lượng này mạnh nhất và dùng nó để chế ngự các nhóm khác. Vua Tự Đức bằng lòng và ban cho Lưu Vĩnh Phúc chức Đề đốc với nhiệm vụ tuần phòng ở biên cảnh. Chính sách này tỏ ra có hiệu quả, quân Cờ Đen giúp sức đánh quân Cờ Vàng, Cờ Trắng và sau này tham gia đánh Pháp.

Năm Tự Đức thứ 24 (1871) vua xuống dụ chuẩn cho ông khôi phục nguyên hàm Thái tử Thái bảo Võ hiển điện Đại học sĩ Trí dõng tướng Tráng liệt bá, nhưng vẫn sung Tam tuyên quân thứ Khâm mạng Đại thần.